Learning rate and attractor size of the single-layer perceptron

We study the simplest possible order one single-layer perceptron with two inputs, using the delta rule with online learning, in order to derive closed form expressions for the mean convergence rates. We investigate the rate of convergence in weight space of the weight vectors corresponding to each of the 14 out of 16 linearly separable rules. These vectors follow zigzagging lines through the piecewise constant vector field to their respective attractors. Based on our studies, we conclude that a single-layer perceptron with $N$ inputs will converge in an average number of steps given by an $N\text{th}$ order polynomial in $\frac{t}{l}$, where $t$ is the threshold, and $l$ is the size of the initial weight distribution. Exact values for these averages are provided for the five linearly separable classes with $N=2$. We also demonstrate that the learning rate is determined by the attractor size, and that the attractors of a single-layer perceptron with $N$ inputs partition ${\mathbb{R}}^N\oplus {\mathbb{R}}^N$.

Figure 1

The solutions of the linear inequalities in Table , corresponding to the attractors of the five learnable classes for the single-layer perceptron. (a) class I representative (0,0,0,0), (b) class II representative (0,0,0,1), (c) class III representative (0,0,1,0), (d) class IV representative (0,0,1,1), and (e) class V representative (0,1,1,1), Note that these regions coincide exactly with the attractors in weight space shown in Fig. 2.

Figure 2

(Color online) The paths in weight space for 250 trials of the converging weight vectors. ×: beginning point of trajectory. *: end point of trajectory. (a) class I representative (0,0,0,0), $\mu =24.47$, $\sigma =22.19$, (b) class II representative (0,0,0,1), $\mu =76.33$, $\sigma =40.80$, (c) class III representative (0,0,1,0), $\mu =43.59$, $\sigma =34.34$, (d) class IV representative (0,0,1,1), $\mu =41.44$, $\sigma =31.04$, and (e) class V representative (0,1,1,1), $\mu =37.91$, $\sigma =27.04$. By calculating the mean and standard deviation of the number of steps over these paths, we arrived at expressions (16, 17, 18, 19, 20, 21, 22, 23, 24, 25).

Figure 3

(Color online) The histograms of the five different classes for 10 000 trials are shown. (a) class I representative (0,0,0,0), $\mu =25.77$, $\sigma =23.98$, (b) class II representative (0,0,0,1), $\mu =77.50$, $\sigma =40.06$, (c) class III representative (0,0,1,0), $\mu =44.39$, $\sigma =35.58$, (d) class IV representative (0,0,1,1), $\mu =40.24$, $\sigma =32.45$, and (e) class V representative (0,1,1,1), $\mu =37.05$, $\sigma =29.22$. Note that four classes have fairly similar shapes, having their distributions weighted towards the left, while the “AND” rule is centrally distributed. Trials which were already in the attractors at $n=0$ were omitted for clarity.

Figure 4

(Color online) Regions $A_1–A_7$ used for calculating Eq. (20) from Eqs. (10, 12). The dashed lines corresponding to $w_1=t$, $w_2=t$, and $w_2=-w_1+t$ partition the initial weight vector space into the seven regions $A_1–A_7$.